/**
 * 请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。
 *
 * 实现 LFUCache 类：
 *
 * LFUCache(int capacity) - 用数据结构的容量capacity 初始化对象
 * int get(int key)- 如果键key 存在于缓存中，则获取键的值，否则返回 -1 。
 * void put(int key, int value)- 如果键key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。
 * 为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。
 *
 * 当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。
 *
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 *
 * 链接：https://leetcode.cn/problems/lfu-cache
 *
 */

/**
 * 上篇文章 算法题就像搭乐高：手把手带你拆解 LRU 算法 写了 LRU 缓存淘汰算法的实现方法，本文来写另一个著名的缓存淘汰算法：LFU 算法。
 *
 * 从实现难度上来说，LFU 算法的难度大于 LRU 算法，因为 LRU 算法相当于把数据按照时间排序，这个需求借助链表很自然就能实现，你一直从链表头部加入元素的话，越靠近头部的元素就是新的数据，越靠近尾部的元素就是旧的数据，我们进行缓存淘汰的时候只要简单地将尾部的元素淘汰掉就行了。
 *
 * 而 LFU 算法相当于是淘汰访问频次最低的数据，如果访问频次最低的数据有多条，需要淘汰最旧的数据。把数据按照访问频次进行排序，而且频次还会不断变化，这可不容易实现。
 *
 * 所以说 LFU 算法要复杂很多，labuladong 进字节跳动的时候就被面试官问到了 LFU 算法。
 */
class LFUCache {
    Map<Integer,Integer> keyToVal;//key到val的映射
    Map<Integer,Integer> keyToFreq;//key到freq的映射
    Map<Integer,LinkedHashSet<Integer>> freqToKey;//freq到key的映射，一对多的关系
    int cap;
    int minFreq;
    public LFUCache(int capacity) {
        this.cap=capacity;
        keyToVal=new HashMap<>();
        keyToFreq=new HashMap<>();
        freqToKey=new HashMap<>();
        this.minFreq=0;
    }
    
    public int get(int key) {
        if(!keyToVal.containsKey(key)) {
            return -1;
        }
        // 增加 key 对应的 freq
        increaseFreq(key);
        return keyToVal.get(key);
    }
    
    public void put(int key, int value) {
        if(this.cap<=0) {
            return;
        }
        /* 若 key 已存在，修改对应的 val 即可 */
        if(keyToVal.containsKey(key)) {
            keyToVal.put(key,value);
            // key 对应的 freq 加一
            increaseFreq(key);
            return;
        }
        /* key 不存在，需要插入 */
    /* 容量已满的话需要淘汰一个 freq 最小的 key */
       if(this.cap<=keyToVal.size()) {
           removeMinFreq();
       }
          /* 插入 key 和 val，对应的 freq 为 1 */
    // 插入 KV 表
       keyToVal.put(key,value);
       //插入KF表
       keyToFreq.put(key,1);
       //插入FK表
       freqToKey.putIfAbsent(1,new LinkedHashSet<>());
       freqToKey.get(1).add(key);
       // 插入新 key 后最小的 freq 肯定是 1
       this.minFreq=1;
    }
    public void increaseFreq(int key) {
         /* 更新 KF 表 */
        int freq=keyToFreq.get(key);
        keyToFreq.put(key,freq+1);
          /* 更新 FK 表 */
    // 将 key 从 freq 对应的列表中删除
        freqToKey.get(freq).remove(key);
          // 将 key 加入 freq + 1 对应的列表中
        freqToKey.putIfAbsent(freq+1,new LinkedHashSet<>());
        freqToKey.get(freq+1).add(key);
        // 如果 freq 对应的列表空了，移除这个 freq
        if(freqToKey.get(freq).isEmpty()) {
            freqToKey.remove(freq);
            if(freq==this.minFreq) {
                this.minFreq++;
            }
        }

    }
    public void removeMinFreq() {
        // freq 最小的 key 列表
        LinkedHashSet<Integer> keyList=freqToKey.get(minFreq);
        // 其中最先被插入的那个 key 就是该被淘汰的 key
        int deleteKey=keyList.iterator().next();
        keyList.remove(deleteKey);
         /* 更新 FK 表 */
        if(keyList.isEmpty()) {
            freqToKey.remove(minFreq);
             // 问：这里需要更新 minFreq 的值吗？
             /**
            答：，如果keyList中只有一个元素，那么删除之后minFreq对应的key列表就为空了，也就是minFreq变量需要被更新。如何计算当前的minFreq是多少呢？
              实际上没办法快速计算minFreq，只能线性遍历FK表或者KF表来计算，这样肯定不能保证 O(1) 的时间复杂度。
              但是，其实这里没必要更新minFreq变量，因为你想想removeMinFreqKey这个函数是在什么时候调用？在put方法中插入新key时可能调用。而你回头看put的代码，插入新key时一定会把minFreq更新成 1，所以说即便这里minFreq变了，我们也不需要管它。 */
        }
        //更新KV表
        keyToVal.remove(deleteKey);
        //更新KF表
        keyToFreq.remove(deleteKey);
    }
}
